The present invention relates to cache memories in computers and more specifically to a cache optimization method.
Computers maintain copies of frequently-used instructions and data in cache memories. Whenever an executing application accesses a line of operating memory, that line is mapped and copied to a slot of the cache memory. The choice of which cache memory slot to use is typically a function of the physical address of the memory line. A performance gain is realized when a computer accesses a needed line from the cache memory, instead of the computer's random-access memory (RAM) or virtual memory.
Because the computer's RAM is always larger than the cache memory, many lines of memory will of necessity map to the same cache memory slot. A collision occurs whenever the cache memory does not contain an accessed memory line and another line must be purged from the slot to make room for the new line. Collisions prevent computers from realizing the full performance potential of their cache memories.
An application that is larger than cache memory is at risk of colliding with itself in the cache memory, even though the cache memory is large enough to hold the frequently-accessed memory lines. The risk is higher in computers that use virtual memory since applications are isolated from knowledge of actual physical addresses. The risk is also higher in multi-tasking environments, since greater demands are put on the cache memory.
The collision problem is much greater today due to layered software development techniques which produce a random distribution of the application working set. The application "working set" is defined as the subset of instructions needed to perform a task. Layered software development simplifies the task of large software development by defining layers of software and assigning a group of developers to each layer. Standard programming techniques then assign contiguous addresses linking code within a given layer. The execution of an application program developed in this way moves from layer to layer.
Large layered application programs running on computers with virtual memory map the working set to the cache memory in a random manner. However, simple statistical analysis shows that random mapping fails to make optimal use of the cache memory. For example, if the size of the working set is equal to the size of the cache memory, a random mapping will on average make use of only sixty-three percent of the cache memory. Thirty-seven percent of the cache memory will on average never be used, even though the cache memory is large enough to hold the entire working set. Thus, collisions occur with an increased risk of line thrashing in code loops.
Therefore, it would be desirable to provide a cache optimization method that minimizes collisions and provides a performance gain over existing cache control methods.